from array import array
from itertools import repeat


class PlanarGrid(object):

    def __init__(self, sizes, create=repeat(None).next):
        x_size, y_size = sizes
        self.__cells = [[create() for y in xrange(y_size)]
                        for x in xrange(x_size)]

    def __getitem__(self, indices):
        x, y = indices
        return self.__cells[x][y]

    def __setitem__(self, indices, value):
        x, y = indices
        self.__cells[x][y] = value


class SpatialGrid(object):

    def __init__(self, sizes, create=repeat(None).next):
        x_size, y_size, z_size = sizes
        self.__cells = [[[create() for z in xrange(z_size)]
                         for y in xrange(y_size)] for x in xrange(x_size)]

    def __getitem__(self, indices):
        x, y, z = indices
        return self.__cells[x][y][z]

    def __setitem__(self, indices, value):
        x, y, z = indices
        self.__cells[x][y][z] = value


class LazyGrid(object):

    def __init__(self, sizes, create=repeat(None).next, clear=None):
        if len(sizes) == 2:
            self.__grid = PlanarGrid(sizes)
        elif len(sizes) == 3:
            self.__grid = SpatialGrid(sizes)
        else:
            raise ValueError('invalid number of sizes')
        self.__create = create
        self.__clear = clear
        self.__tag = 0

    def clear(self):
        self.__tag += 1

    def __getitem__(self, indices):
        cell = self.__grid[indices]
        if cell is None:
            cell = self.__grid[indices] = [self.__tag, self.__create()]
        elif cell[0] != self.__tag:
            cell[0] = self.__tag
            if self.__clear is None:
                cell[1] = self.__create()
            else:
                self.__clear(cell[1])
        return cell[1]

    def __setitem__(self, indices, value):
        cell = self.__grid[indices]
        if cell is None:
            self.__grid[indices] = [self.__tag, value]
        else:
            cell[0] = self.__tag
            cell[1] = value


class GridSet(object):

    def __init__(self, size):
        width, height = size
        self.__tag = 1
        self.__cells = [array('i', repeat(0, height)) for x in xrange(width)]

    def __contains__(self, pos):
        x, y = pos
        return self.__cells[x][y] == self.__tag

    def add(self, pos):
        x, y = pos
        self.__cells[x][y] = self.__tag

    def remove(self, pos):
        x, y = pos
        self.__cells[x][y] = 0

    def clear(self):
        self.__tag += 1
